#define _CRT_SECURE_NO_WARNINGS 

#include<iostream>
using namespace std;

namespace lh
{
	//BM11链表相加（二）
	//https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=295&tqId=1008772&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };


    class Solution {
    public:

        ListNode* reserveList(ListNode* head)
        {
            if (head == nullptr)
                return nullptr;
            ListNode* cur = head;
            ListNode* pre = nullptr;
            while (cur != nullptr)
            {
                //断连接前保存当前指针下一个
                ListNode* tmp = cur->next;
                cur->next = pre;

                pre = cur;
                cur = tmp;
            }
            return pre;
        }

        ListNode* addInList(ListNode* head1, ListNode* head2) {
            // write code here
            //思路：因为链表没法倒着遍历，反转两链表实现低位先计算（倒着遍历）。
            //结果再反转得到正常结果数
            if (head1 == nullptr)
                return head2;
            if (head2 == nullptr)
                return head1;
            //反转两链表
            ListNode* cur1 = reserveList(head1);
            ListNode* cur2 = reserveList(head2);
            //结果链表，表头
            ListNode* res = new ListNode(-1);
            ListNode* head = res;

            int carry = 0;
            while (cur1 != nullptr || cur2 != nullptr || carry == 1)
            {
                int val1 = cur1 == nullptr ? 0 : cur1->val;
                int val2 = cur2 == nullptr ? 0 : cur2->val;
                //相加
                int tmp = val1 + val2 + carry;
                //获取进位
                carry = tmp / 10;
                tmp = tmp % 10;
                //添加节点
                head->next = new ListNode(tmp);
                head = head->next;
                //遍历相加链表
                if (cur1)
                {
                    cur1 = cur1->next;
                }
                if (cur2)
                {
                    cur2 = cur2->next;
                }
            }
            res = reserveList(res->next);
            return res;

        }
    };
    void test1()
    {
        ListNode* node1 = new ListNode(9);
        ListNode* node2 = new ListNode(3);
        ListNode* node3 = new ListNode(7);
        ListNode* node4 = new ListNode(6);
        ListNode* node5 = new ListNode(3);

        node1->next = node2;
        node2->next = node3;

        node4->next = node5;
        //9->3->7
        //   6->3
        ListNode* res = Solution().addInList(node1, node4);
        ListNode* cur = res;
        while (cur)
        {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << endl;
        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;

    }
    //BM12 单链表的排序
    //https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=295&tqId=1008897&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        /**
         *
         * @param head ListNode类 the head node
         * @return ListNode类
         */
         //合并两个有序链表
        ListNode* merge(ListNode* pHead1, ListNode* pHead2)
        {
            if (pHead1 == nullptr)
                return pHead2;
            if (pHead2 == nullptr)
                return pHead1;
            //表头
            ListNode* res = new ListNode(-1);
            ListNode* cur = res;
            while (pHead1 && pHead2)
            {
                if (pHead1->val <= pHead2->val)
                {
                    cur->next = pHead1;
                    pHead1 = pHead1->next;
                }
                else {
                    cur->next = pHead2;
                    pHead2 = pHead2->next;
                }
                cur = cur->next;
            }
            if (pHead1)
                cur->next = pHead1;
            if (pHead2)
                cur->next = pHead2;
            return res->next;
        }

        ListNode* sortInList(ListNode* head) {
            // write code here
            if (head == nullptr || head->next == nullptr)
            {
                return head;
            }
            //快慢指针,2倍,保证中间划分
            ListNode* left = head;
            ListNode* mid = head->next;
            ListNode* right = head->next->next;
            //当右指针到达尾部，中间指针指向链表中间
            while (right && right->next)
            {
                left = left->next;
                mid = mid->next;
                right = right->next->next;
            }
            //断开左部与右部连接
            left->next = nullptr;
            //合并排好序的两段
            return merge(sortInList(head), sortInList(mid));
        }
    };
    void test2()
    {
        ListNode* node1 = new ListNode(1);
        ListNode* node2 = new ListNode(3);
        ListNode* node3 = new ListNode(2);
        ListNode* node4 = new ListNode(4);
        ListNode* node5 = new ListNode(5);
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;

        ListNode* res = Solution2().sortInList(node1);
        ListNode* cur = res;
        while (cur)
        {
            cout << cur->val << "->";
            cur = cur->next;
        }
        cout << endl;
        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
    }
};

int main()
{
    lh::test1();
    lh::test2();
    return 0;
}